package com.example.ymm;

import java.util.*;

public class MenuFilter {

    // 菜单节点类
    static class MenuNode {
        private Integer id;
        private String name;
        private List<MenuNode> children;

        public MenuNode(Integer id, String name) {
            this.id = id;
            this.name = name;
            this.children = new ArrayList<>();
        }

        public Integer getId() {
            return id;
        }

        public String getName() {
            return name;
        }

        public List<MenuNode> getChildren() {
            return children;
        }

        public void addChild(MenuNode child) {
            this.children.add(child);
        }

        @Override
        public String toString() {
            return "MenuNode{id=" + id + ", name='" + name + "'}";
        }
    }

    // 过滤树形菜单的方法 - 优化去重逻辑
    public static List<MenuNode> filterMenuByIDs(List<MenuNode> menuNodes, Set<Integer> allowedIds) {
        // 用于跟踪已处理的节点ID
        Set<Integer> processedIds = new HashSet<>();
        // 存储最终结果
        List<MenuNode> result = new ArrayList<>();

        for (MenuNode node : menuNodes) {
            MenuNode filteredNode = filterNode(node, allowedIds, processedIds);
            if (filteredNode != null) {
                result.add(filteredNode);
            }
        }
        return result;
    }

    private static MenuNode filterNode(MenuNode node, Set<Integer> allowedIds, Set<Integer> processedIds) {
        // 如果节点已处理，跳过处理以避免重复
        if (processedIds.contains(node.getId())) {
            return null;
        }

        // 标记节点为已处理
        processedIds.add(node.getId());

        // 创建新节点
        MenuNode newNode = new MenuNode(node.getId(), node.getName());

        // 标记是否有子节点符合条件
        boolean hasValidChild = false;

        // 递归过滤子节点
        for (MenuNode child : node.getChildren()) {
            MenuNode filteredChild = filterNode(child, allowedIds, processedIds);
            if (filteredChild != null) {
                newNode.addChild(filteredChild);
                hasValidChild = true;
            }
        }

        // 如果当前节点ID在允许列表中，或者有符合条件的子节点，则保留该节点
        if (allowedIds.contains(node.getId()) || hasValidChild) {
            return newNode;
        }

        // 否则不保留
        return null;
    }

    public static void main(String[] args) {
        // 构建示例菜单树（包含重复路径）


        MenuNode root2 = new MenuNode(2, "内容管理");
        MenuNode child21 = new MenuNode(21, "文章管理");
        MenuNode child22 = new MenuNode(22, "评论管理");
        root2.addChild(child21);
        root2.addChild(child22);

        MenuNode root1 = new MenuNode(1, "系统管理");
        MenuNode child11 = new MenuNode(11, "用户管理");
        MenuNode child12 = new MenuNode(12, "角色管理");
        root1.addChild(child11);
        root1.addChild(child12);
        root1.addChild(root2);

        // 创建重复引用（模拟可能的重复路径）
        MenuNode duplicateRoot = new MenuNode(1, "系统管理"); // ID重复
        duplicateRoot.addChild(child11); // 重复引用child11

        List<MenuNode> menuTree = Arrays.asList(root1, root2, duplicateRoot);

        // 定义允许的菜单ID列表
        Set<Integer> allowedIds = new HashSet<>(Arrays.asList(11, 22));

        // 过滤菜单树
        List<MenuNode> filteredMenu = filterMenuByIDs(menuTree, allowedIds);

        // 输出结果
        System.out.println("过滤后的菜单树:");
        printMenuTree(filteredMenu, 0);
    }

    // 辅助方法：打印菜单树
    private static void printMenuTree(List<MenuNode> menuNodes, int level) {
        for (MenuNode node : menuNodes) {
            StringBuilder indent = new StringBuilder();
            for (int i = 0; i < level; i++) {
                indent.append("  ");
            }
            System.out.println(indent + node.toString());
            printMenuTree(node.getChildren(), level + 1);
        }
    }
}
